package tulingxueyuan117;

import java.util.HashMap;
import java.util.Map;

/**
 * Author: Zhang Dongwei
 * Date: 2022/10/17 20:44
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 */
public class p5_爬楼梯_70_re {
    public static void main(String[] args) {
        int n = 5;
        int res = climbStairs(n);
        System.out.println(res);
    }
// 超时, 时间复杂度O(2^n)
    public static int climbStairs1(int n) {
        if(n<0) return 0;
        else if(n==1) return 1;
        else if(n==2) return 2;
        else return climbStairs(n-1)+climbStairs(n-2);
    }

//    引入hashmap，复杂度O(n)
    private static Map<Integer, Integer> map = new HashMap<>();
    public static int climbStairs2(int n) {
        if(n<0) return 0;
        else if(n==1) return 1;
        else if(n==2) return 2;
        else {
            if(map.get(n)!=null) return map.get(n);
            else {
                map.put(n, climbStairs(n-1)+climbStairs(n-2));
                return climbStairs(n-1)+climbStairs(n-2);
            }
        }
    }


    public static int climbStairs(int n) {
        if(n<0) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        int pre = 2;
        int prepre = 1;
        int res = 0;
        for(int i=3; i<=n; i++){
            res = pre + prepre;
            prepre = pre;
            pre = res;
        }
        return res;
    }
}
